package com.zxy.javaarithmetic.chapter_1_StackQueue;

import java.util.HashMap;
import java.util.Stack;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_1_StackQueue
 *  @文件名:   P_8_GetArrayMaxTree
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/3 13:39
 *  @描述：    给定一个无重复元素的数组arr,写出生成该数组的MaxTree的函数。要求如果数组长度为N,则时间复杂度为O(N),额外空间复杂度为O(N).MaxTree定义如下：
 *            1、数组没有重复元素；2、MaxTree是一棵二叉树，数组每一个值对应一个二叉树节点；3、包括MaxTree在内且在其中的每一个子树上值最大的节点都是树的头；
 */
public class P_8_GetArrayMaxTree {

	public static void main(String[] args) {
		Node node = getArrMaxTree(new int[]{3, 4, 5, 1, 2});
		printPreOrder(node);
		System.out.println();
		printInOrder(node);
		System.out.println();
	}

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int value) {
			this.value = value;
		}
	}

	public static Node getArrMaxTree(int[] arr) {
		//利用Stack来判断获取数组每一个值向左或向右第一个大于该值的数
		Stack<Node> stack = new Stack<>();
		HashMap<Node, Node> lBigMap = new HashMap<>();
		HashMap<Node, Node> rBigMap = new HashMap<>();

		Node[] nodes = new Node[arr.length];
		for (int i = 0; i < arr.length; i++) {
			nodes[i] = new Node(arr[i]);
		}

		//		for (int i = 0; i < nodes.length; i++) {
		//			Node node = nodes[i];
		//
		//			while (!stack.isEmpty() && stack.peek().value < node.value) {
		//				stack.pop();
		//			}
		//			if (!stack.isEmpty()) {
		//				lBigMap.put(node, stack.peek());
		//			} else {
		//				lBigMap.put(node, null);
		//			}
		//
		//			stack.push(node);
		//		}
		//
		//		stack.clear();

		for (int i = 0; i < nodes.length; i++) {
			Node node = nodes[i];

			while (!stack.isEmpty() && stack.peek().value < node.value) {
				popStackSetMap(stack, lBigMap);
			}

			stack.push(node);
		}

		while (!stack.isEmpty()) {
			popStackSetMap(stack, lBigMap);
		}

		//		for (int i = nodes.length - 1; i >= 0; i--) {
		//			Node node = nodes[i];
		//
		//			while (!stack.isEmpty() && stack.peek().value < node.value) {
		//				stack.pop();
		//			}
		//			if (!stack.isEmpty()) {
		//				rBigMap.put(node, stack.peek());
		//			} else {
		//				rBigMap.put(node, null);
		//			}
		//
		//			stack.push(node);
		//		}

		for (int i = nodes.length - 1; i >= 0; i--) {
			Node node = nodes[i];
			while (!stack.isEmpty() && stack.peek().value < node.value) {
				popStackSetMap(stack, rBigMap);
			}
			stack.push(node);
		}

		while (!stack.isEmpty()) {
			popStackSetMap(stack, rBigMap);
		}

		Node head = null;
		for (int i = 0; i < nodes.length; i++) {
			Node cur = nodes[i];
			Node left = lBigMap.get(cur);
			Node right = rBigMap.get(cur);
			if (left == null && right == null) {
				head = cur;
			} else if (right == null) {
				if (left.left == null) {
					left.left = cur;
				} else {
					left.right = cur;
				}
			} else if (left == null) {
				if (right.left == null) {
					right.left = cur;
				} else {
					right.right = cur;
				}
			} else if (left.value < right.value) {
				if (left.left == null) {
					left.left = cur;
				} else {
					left.right = cur;
				}
			} else {
				if (right.left == null) {
					right.left = cur;
				} else {
					right.right = cur;
				}
			}
		}
		return head;
	}

	public static void popStackSetMap(Stack<Node> stack, HashMap<Node, Node> map) {
		Node popNode = stack.pop();
		if (!stack.isEmpty()) {
			map.put(popNode, stack.peek());
		} else {
			map.put(popNode, null);
		}
	}

	public static void printPreOrder(Node head) {
		if (head == null) {
			return;
		}
		System.out.print(head.value + " ");
		printPreOrder(head.left);
		printPreOrder(head.right);
	}

	public static void printInOrder(Node head) {
		if (head == null) {
			return;
		}
		printPreOrder(head.left);
		System.out.print(head.value + " ");
		printPreOrder(head.right);
	}

	public static int[] randomCommon(int min, int max, int n) {
		if (n > (max - min + 1) || max < min) {
			return null;
		}
		int[] result = new int[n];
		int count = 0;
		while (count < n) {
			int num = (int) (Math.random() * (max - min)) + min;
			boolean flag = true;
			for (int j = 0; j < n; j++) {
				if (num == result[j]) {
					flag = false;
					break;
				}
			}
			if (flag) {
				result[count] = num;
				count++;
			}
		}
		return result;
	}

}
